package com.xiaolin.structure.linked.oneway;

/**
 * @ClassName OneWayLinkedList
 * @Description 单向链表
 * @Detail detail
 * @Author MyPC
 * @Date 2020/11/5
 * @Version 1.0
 */
public class OneWayLinkedList<E> {
    int size;
    Node<E> first;
    Node<E> last;

    /**
     * 关联链表的节点
     * @param e
     */
    private void linkedElement(E e){
        Node<E> f=this.first;
        if(f == null){
            //此链表没有任何节点，则存储第一个节点
            this.first=new Node<>(e,null);
            size++;
        }else {
            // 此链表有节点，将新元素插入到最后
            //用于存储原来的最后一个节点
            Node<E> temp=null;
            //如果f为null，则表明temp已经保存了最后一个节点
            while (f != null){
                temp=f;
                f=f.next;
            }
            temp.next=new Node<>(e,null);
            //保存新的最后一个节点
            this.last=temp.next;
            size++;
        }
    }

    /**
     * 校验索引
     * @param index
     */
    private void indexCheckout(int index){
        if(index<0 || index >=size){
            throw new IndexOutOfBoundsException("索引越界");
        }
    }

    /**
     * 根据索引获取节点
     * @param index
     * @return
     */
    private Node<E> getNode(int index){
        Node<E> f=this.first;
        for (int i=1;i<=index;i++){
            f=f.next;
        }
        return f;
    }

    /**
     * 获取索引的前一个节点
     * @param index
     * @return
     */
    private Node<E> getPreNode(int index){
        //只有索引大于0才有前一个节点
        if(index <= 0){
            return null;
        }
        Node<E> f=this.first;
        for (int i=1;i<=index-1;i++){
            f=f.next;
        }
        return f;
    }

    /**
     * 添加元素
     * @param e
     * @return
     */
    public boolean add(E e){
        linkedElement(e);
        return true;
    }

    /**
     * 根据索引获取元素
     * @param index
     * @return
     */
    public E get(int index){
        indexCheckout(index);
        return getNode(index).item;
    }

    /**
     * 根据索引移除节点
     * @param index
     * @return
     */
    public boolean remove(int index){
        indexCheckout(index);
        if(index == 0){
            //移除第一个
            this.first=this.first.next;
            size--;
        }else if(index > 0 && index == size-1){
            //移除最后一个
            this.last=getPreNode(index);
            this.last.next=null;
            size--;
        }else {
            //移除中间节点
            Node<E> preNode = this.getPreNode(index);
            preNode.next=this.getNode(index).next;
            size--;
        }
        return true;
    }

}
